package easy;

public class leetcode14_longestCommonPrefix {
    /*编写一个函数来查找字符串数组中的最长公共前缀。
        如果不存在公共前缀，返回空字符串 ""。
    */

    /**
     * 分析：
     *      们要想寻找最长公共前缀，那么首先这个前缀是公共的，我们可以从任意一个元素中找到它。
     * 假定我们现在就从一个数组中寻找最长公共前缀，那么首先，我们可以将第一个元素设置为基准
     * 元素x0。假如数组为["flow","flower","flight"]，flow就是我们的基准元素x0。
     * 然后我们只需要依次将基准元素和后面的元素进行比较（假定后面的元素依次为x1,x2,x3....），不断更
     * 新基准元素，直到基准元素和所有元素都满足最长公共前缀的条件，就可以得到最长公共前缀。
     * 具体比对过程如下：
     * 如果strings.Index(x1,x) == 0，则直接跳过（因为此时x就是x1的最长公共前缀），对比下一个元
     * 素。（如flower和flow进行比较）
     * 如果strings.Index(x1,x) != 0, 则截取掉基准元素x的最后一个元素，再次和x1进行比较，直至满足
     * string.Index(x1,x) == 0，此时截取后的x为x和x1的最长公共前缀。（如flight和flow进行比较，依
     * 次截取出flow-flo-fl，直到fl被截取出，此时fl为flight和flow的最长公共前缀）
     */
    public static void main(String[] args) {
        System.out.println(longestCommonPrefix(new String[]{"flower", ""}));
    }


//    public static String longestCommonPrefix(String[] strs) {
//        // 使用字符串的charAt方法
//        String str = "";
//        // 数组长度为1时
//        if (strs.length == 1) {
//            if (!"".equals(strs[0])) {
//                str += strs[0].charAt(0);
//            }
//            return str;
//        }
//        // 判断数组中最短字符串
//        int min = strs[0].length();
//        for (String s : strs) {
//            if (min > s.length()) {
//                min = s.length();
//            }
//        }
//
//        // 遍历数组
//        for (int i = 0; i < min; i++) {
//            for (int j = 0; j < strs.length - 1; j++) {
//                // 对数组的值进行判空处理
//                if ("".equals(strs[j])) {
//                    return "";
//                }
//                // 取出字符串的第一个字符
//                char ch = strs[j].charAt(i);
//                if (ch != strs[j + 1].charAt(i)) {
//                    return str;
//                }
//            }
//            str += strs[0].charAt(i);
//        }
//
//
//        return str;
//    }
    public static String longestCommonPrefix(String[] strs) {
        // 判断字符串数组是否为空，或者长度是否为0
        // 如为空或0 则返回空字符串
        if (strs == null || strs.length == 0) {
            return "";
        }
        String prefix = strs[0];
        int count = strs.length;
        for (int i = 1; i < count; i++) {
            // 调用所写查找方法
            prefix = longestCommonPrefix(prefix, strs[i]);
            // 如果字符串数组中存在空字符串即字符串长度为0 则跳出循环
            if (prefix.length() == 0) {
                break;
            }
        }
        return prefix;
    }

    // 查找两个字符串的公共前缀
    public static String longestCommonPrefix(String str1, String str2) {
        // 对于两个字符串中取长度较小的
        int length = Math.min(str1.length(), str2.length());
        int index = 0;
        // 判断字符串前缀是否相等
        while (index < length && str1.charAt(index) == str2.charAt(index)) {
            index++;
        }
        // 返回相同的前缀
        // substring(start,end)方法 用于截取字符串
        return str1.substring(0, index);
    }


}
